package com.origin.niuke.binarySearch;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/24 21:32
 * 在两个长度相等的排序数组中找到上中位数
 * 给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
 * 上中位数：假设递增序列长度为n，为第n/2个数
 * 算法：二分查找
 * 因为数组有序，又是查找数组，应该先想到二分查找
 * 比较 arr1[mid1] 和 arr2[mid2]
 * 当 arr1[mid1] = arr2[mid2], 直接返回 arr1[mid1]
 * 当 arr1[mid1] > arr2[mid2],
 *     当 n 为奇数时, 中位数只会出现在 arr1 的 [0, mid1] 和 arr2 的 [mid2, n - 1]
 *     当 n 为偶数时, 中位数只会出现在 arr1 的 [0, mid1] 和 arr2 的 (mid2, n - 1]
 * 当 arr1[mid1] < arr2[mid2],
 *     当 n 为奇数时, 中位数只会出现在 arr1 的 [mid1, n - 1] 和 arr2 的 [0, mid1]
 *     当 n 为偶数时, 中位数只会出现在 arr1 的 (mid1, n - 1] 和 arr2 的 [0, mid2]
 */
public class NC36 {

    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int l1 = 0, l2 = 0, r1 = arr1.length - 1, r2 = arr2.length - 1;
        while (l1 < r1) {
            int mid1 = l1 + (r1 - l1) / 2;
            int mid2 = l2 + (r2 - l2) / 2;
            int k = (r1 - l1 + 1) / 2 == 0 ? 1 : 0;
            if (arr1[mid1] == arr2[mid2]) return arr1[mid1];
            else if (arr1[mid1] > arr2[mid2]) {
                r1 = mid1;
                l2 = mid2 + k;
            } else {
                l1 = mid1 + k;
                r2 = mid2;
            }
        }
        return Math.min(arr1[l1], arr2[l2]);
    }

}
